Find the maximum value of length(word[i])*length(word[j])

Time: O(N)~O(N^2); Space: O(N); medium

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:

Input: [“abcw”, “baz”, “foo”, “bar”, “xtfn”, “abcdef”]

Output: 16

The two words can be “abcw”, “xtfn”.

Example 2:

Input: [“a”, “ab”, “abc”, “d”, “cd”, “bcd”, “abcd”]

Output: 4

Explanation:

  • The two words can be “ab”, “cd”.

Example 3:

Input: [“a”, “aa”, “aaa”, “aaaa”]

Output: 0

Follow up:

  • Could you do better than O(n2), where n is the number of words?

[1]:

class Solution1(object):
    """
    Counting Sort + Pruning + Bit Manipulation
    """
    def maxProduct(self, words) -> int:
        """
        :type words: List[str]
        :rtype: int
        """
        def counting_sort(words):
            k = 1000  # k is max length of words in the dictionary
            buckets = [[] for _ in range(k)]
            for word in words:
                buckets[len(word)].append(word)
            res = []
            for i in reversed(range(k)):
                if buckets[i]:
                    res += buckets[i]
            return res

        words = counting_sort(words)
        bits = [0] * len(words)
        for i, word in enumerate(words):
            for c in word:
                bits[i] |= (1 << (ord(c) - ord('a')))

        max_product = 0
        for i in range(len(words) - 1):
            if len(words[i]) ** 2 <= max_product:
                break
            for j in range(i + 1, len(words)):
                if len(words[i]) * len(words[j]) <= max_product:
                    break
                if not (bits[i] & bits[j]):
                    max_product = len(words[i]) * len(words[j])
        return max_product

[2]:

s = Solution1()
assert s.maxProduct(["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]) == 16
assert s.maxProduct(["a", "ab", "abc", "d", "cd", "bcd", "abcd"]) == 4
assert s.maxProduct(["a", "aa", "aaa", "aaaa"]) == 0

[3]:

class Solution2(object):
    # Time: O(NlogN) ~ O(N^2); Space: O(N)
    # Sorting + Pruning + Bit Manipulation
    def maxProduct(self, words) -> int:
        """
        :type words: List[str]
        :rtype: int
        """
        words.sort(key=lambda x: len(x), reverse=True)
        bits = [0] * len(words)

        for i, word in enumerate(words):
            for c in word:
                bits[i] |= (1 << (ord(c) - ord('a')))

        max_product = 0
        for i in range(len(words) - 1):
            if len(words[i]) ** 2 <= max_product:
                break
            for j in range(i + 1, len(words)):
                if len(words[i]) * len(words[j]) <= max_product:
                    break
                if not (bits[i] & bits[j]):
                    max_product = len(words[i]) * len(words[j])

        return max_product

[4]:

s = Solution2()
assert s.maxProduct(["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]) == 16
assert s.maxProduct(["a", "ab", "abc", "d", "cd", "bcd", "abcd"]) == 4
assert s.maxProduct(["a", "aa", "aaa", "aaaa"]) == 0